package com.monday.greedy.algorithm;

/**
 * 在一个非负整数 a 中，我们希望从中移除 k 个数字，让剩下的数字值最小，如何选择移除哪 k 个数字呢？
 */
public class RemoveNumberToMinimiseTheValue {

    /**
     * 删除整数k个数字,让剩下数字最小
     * <p>
     * 每一轮从左到右比较前一个数字后一个数字,如果前者比后者大,则删除前者。如果都不满足则删除最后一位
     *
     * @param originValue    ： 整数
     * @param numOfDeletions ： 删除数
     */
    public void removeNumToMinimiseTheValue(int originValue, int numOfDeletions) {
        if (String.valueOf(originValue).length() < numOfDeletions) {
            System.err.println("参数错误");
            return;
        }

        StringBuilder str = new StringBuilder().append(originValue);
        System.out.println("====>原始数据:" + str + ",删除位数:" + numOfDeletions);

        for (int k = 0; k < numOfDeletions; k++) {
            int deleteIndex = str.length() - 1;
            for (int i = 0; i < str.length() - 1; i++) {
                char former = str.charAt(i);
                char latter = str.charAt(i + 1);
                if (former > latter) {
                    deleteIndex = i;
                    break;
                }
            }
            str.deleteCharAt(deleteIndex);
            System.out.println("第" + (k + 1) + "轮删除后:" + str);
        }

    }
}
